package set.src;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

import set.CMDR.SnapshotCounter;


/**
 * 
 * @author Erik Sapir & Lior Zibi
 * 
 * Fine-grained synchronization: lock coupling (hand-over-hand locking).
 * 
 * @param T Item type.
 */
public class FineList<T> implements Set<T>{
	
	/**
	 * First list entry
	 */
	volatile private Node m_head;
   
	/**
	 * counter for number of element in the list
	 */
	volatile private SnapshotCounter m_counter;
	
	/**
	 * number of threads using the list
	 */
	final private int m_numOfThreads;
	
	/**
	 * Constructor
	 */
	public FineList(int numOfThreads) {
		System.out.println("\n\tSet Is: Fine List\n");
		
		// Add sentinels to start and end
		m_head      = new Node(Integer.MIN_VALUE);
		m_head.m_next = new Node(Integer.MAX_VALUE);
		m_counter = new SnapshotCounter(numOfThreads);
		
		//save number of threads - will be used in clean method
		m_numOfThreads = numOfThreads;
	}
  
	public boolean add(T item, int threadID) {
		
		int key = item.hashCode();
		
		m_head.lock();
		
		//save the counter in this point.
		//if clean method will be called during function run than
		//incrementing this counter will have no influence
		//on the new counter.
		SnapshotCounter pToCounter = m_counter;
		
		Node pred = m_head;
		
		try {
			
			Node curr = pred.m_next;
			curr.lock();
			try {
				//find the first element equal or greater to the new element to be added.
				//do it using the hand-by-hand locking
				while (curr.m_key < key) {
					pred.unlock();
					pred = curr;
					curr = curr.m_next;
					curr.lock();
				}
				
				//check if element already exist in list - is so, return false
				if (curr.m_key == key) {
					return false;
				}
				
				//add the new element to list
				Node newNode = new Node(item);
				newNode.m_next = curr;
				pred.m_next = newNode;
	        
				//added successfully - increment number of elements in list
				pToCounter.inc(threadID);
	        
				return true;
			} finally {
				curr.unlock(); //always unlock
			}
		} finally {
			pred.unlock(); //always unlock
		}
	}
	
	public boolean remove(T item, int threadID) {
	  
		Node pred = null, curr = null;
		int key = item.hashCode();
		
		
		m_head.lock();
		
		//save the counter in this point.
		//if clean method will be called during function run than
		//incrementing this counter will have no influence
		//on the new counter.
		SnapshotCounter pToCounter = m_counter;
		
		pred = m_head;
		
		try {
			
			curr = pred.m_next;
			curr.lock();
			
			try {
				
				//find the first element equal or greater to the new element to be removed.
				//do it using the hand-by-hand locking
				while (curr.m_key < key) {
					pred.unlock();
					pred = curr;
					curr = curr.m_next;
					curr.lock();
				}
				
				if (curr.m_key == key) {
					//remove element from list
					pred.m_next = curr.m_next;
					
					//element removed successfully - decrement number of element in list
					pToCounter.dec(threadID);
	          
					return true;
				}
	
				//element not found in list - nothing to remove
				return false;
				
			} finally {
				curr.unlock(); //always unlock
			}
		} finally {
			pred.unlock(); //always unlock
		}
	}
	
	public boolean contains(T item, int threadID) {
		Node pred = null, curr = null;
		int key = item.hashCode();
		
		m_head.lock();
    
		pred = m_head;
		
		try {
			
			curr = pred.m_next;
			curr.lock();
			try {
				
				//find the first element equal or greater to the element we are searching.
				//do it using the hand-by-hand locking
				while (curr.m_key < key) {
					pred.unlock();
					pred = curr;
					curr = curr.m_next;
					curr.lock();
				}
				
				//return true iff element found in list
				return (curr.m_key == key);
			} finally {
				curr.unlock(); //always unlock
			}
		} finally {
			pred.unlock(); //always unlock
		}
	}

	public void clean(int threadID) {
		m_head.lock();
		
		try {
			//build new tail and set head.next to tail.
			//all old elements are removed from list because
			//they are not reachable from head anymore.
			m_head.m_next = new Node(Integer.MAX_VALUE);
			
			//use new counter - much easier that setting number
			//of element in list to '0'
			m_counter = new SnapshotCounter(m_numOfThreads);
		} finally {
			m_head.unlock(); //always unlock
		}
	}
	
	public boolean isEmpty(int threadID) {
		
		m_head.lock();
		
		try {
			
			m_head.m_next.lock();
			
			try {
				//if head is pointing to tail, than list in empty
				return (m_head.m_next.m_key == Integer.MAX_VALUE);
			}
			finally {
				m_head.m_next.unlock(); //always unlock
			}
		}
		finally {
			
			m_head.unlock(); //always unlock
		}
	}

	public int size(int threadID) {
		return m_counter.scan_sum();	
	}

	/**
	 * 	list Node
	 */
	private class Node {
		/**
		 * actual item
		 */
		final T m_item;
			
		/**
		 * item's hash code
		 */
		final int m_key;
  
		/**
		 * next Node in list
		 */
		volatile Node m_next;
		
		/**
		 * synchronizes individual Node
		 */
		Lock m_lock;
  
		/**
		 * Constructor for usual Node
		 * @param item element in list
		 */
		Node(T item) {
			this.m_item = item;
			this.m_key = item.hashCode();
			this.m_lock = new ReentrantLock();
		}
		
		/**
		 * Constructor for sentinel Node
		 *@param key should be min or max int value
		 */
		Node(int key) {
			this.m_item = null;
			this.m_key = key;
			this.m_lock = new ReentrantLock();
		}
		
		/**
		 * Lock Node
		 */
		void lock() {m_lock.lock();}

		/**
		 * Unlock Node
		 */
		void unlock() {m_lock.unlock();}
	}
}

